/*
24. 打家劫舍3
2022-10-30
link: https://leetcode.cn/problems/house-robber-iii/
question:
	在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
	这个地区只有一个入口，我们称之为“根”。 除了“根”之外，
	每栋房子有且只有一个“父“房子与之相连。
	一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
	如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
	计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
answer:
	注意：房屋排列从数组变成了树。
	树的遍历有前中后序（深度优先搜索）和层序遍历（广度优先搜索）。

	1、本题一定要后序遍历，因为通过递归函数的返回值来做下一步计算。
	2、关于当前节点抢与不抢的讨论：
		如果抢了当前节点，两个孩子就不能动，
		如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）

	树形dp的入门题目，即在树上进行递归公式的推导。
	将递归三部曲和动态规划五步曲结合起来，解决本题。
	1、确定递归函数的参数和返回值：
		参数为当前节点，返回值是以长度为2的数组。
		要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
		实际是dp数组，下标含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
		(在递归的过程中，系统栈会保存每一层递归的参数。进而长度为2的数组可以标记树中每个节点的状态。)
	2、确定终止条件：
	在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回。
	即dp数组的初始化。
	3、确定遍历顺序
	明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
	通过递归左节点，得到左节点偷与不偷的金钱。
	通过递归右节点，得到右节点偷与不偷的金钱。
	4、确定单层递归的逻辑[重点]
	如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就在回顾一下dp数组的含义）
	如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
	最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
	5、举例推导dp数组
*/
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
	res := robTree(root)
	return max(res[0], res[1])
}

func robTree(cur *TreeNode) []int {
	if cur == nil {
		return []int{0, 0}
	}
	// 后序遍历
	left := robTree(cur.Left)
	right := robTree(cur.Right)
	// 考虑去偷当前的屋子
	robCur := cur.Val + left[0] + right[0]
	// 考虑不偷当前的屋子
	notRobCur := max(left[0], left[1]) + max(right[0], right[1])
	// 注意顺序：0不偷， 1偷
	return []int{notRobCur, robCur}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}